Voir

Comparaison entre ancien et nouveau modèle[modifier | modifier le code]

Problème lié	Base de données
Structure des données	arbre

Découvreur ou inventeur	Andrew Viterbi
Problème lié	Algorithme

Découvreur ou inventeur	Andrew Viterbi
Problème lié	Algorithme

Algorithme de Viterbi[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

nouveau modèle actuel[modifier | modifier le code]

Arbre B[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Arbre B

Exemple d'un 3-5 B-arbre

Découvreurs ou inventeurs	Rudolf Bayer, Edward M. McCreight
Date de découverte	1972^[1]
Problème lié	Structure de données
Structure des données	Arbre enraciné

Complexité en temps
Pire cas	$O(\log n)(insertion)$ , $O(\log n)(suppression)$ , $O(\log n)(recherche)$
Moyenne	$O(\log n)$ , $O(\log n)$ , $O(\log n)$

Complexité en espace
Pire cas	$O(n)$
Moyenne	$O(n)$

nouveau modèle actuel[modifier | modifier le code]

Arbre B

Exemple d'un 3-5 B-arbre

Découvreurs ou inventeurs	Rudolf Bayer, Edward M. McCreight
Date de découverte	1972^[1]
Problème lié	Structure de données
Structure des données	Arbre enraciné

Complexité en temps
Pire cas	$O(\log n)(insertion)$ , $O(\log n)(suppression)$ , $O(\log n)(recherche)$
Moyenne	$O(\log n)$ , $O(\log n)$ , $O(\log n)$

Complexité en espace
Pire cas	$O(n)$
Moyenne	$O(n)$

RIPEMD-160[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

RIPEMD-160

Problème lié	fonction de hachage

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

RIPEMD-160

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

nouveau modèle actuel[modifier | modifier le code]

RIPEMD-160

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1996
Problème lié	Fonction de hachage cryptographique
Basé sur	RIPEMD, MD4

RIPEMD[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Pas de modèle utilisé

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

RIPEMD

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1992
Problème lié	Fonction de hachage cryptographique
À l'origine de	RIPEMD-160, RIPEMD-256, RIPEMD-128, RIPEMD-320 (en)

nouveau modèle actuel[modifier | modifier le code]

RIPEMD

Un sous-bloc de la fonction de compression de l'algorithme de hachage RIPEMD-160

Découvreurs ou inventeurs	Hans Dobbertin, Antoon Bosselaers (d), Bart Preneel
Date de découverte	1992
Problème lié	Fonction de hachage cryptographique
À l'origine de	RIPEMD-160, RIPEMD-256, RIPEMD-128, RIPEMD-320 (en)

EdgeRank[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

EdgeRank

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

EdgeRank

Découvreur ou inventeur	Meta
Date de découverte	2007
Problème lié	Algorithme

nouveau modèle actuel[modifier | modifier le code]

EdgeRank

Découvreur ou inventeur	Meta
Date de découverte	2007
Problème lié	Algorithme

Arbre de Van Emde Boas[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Arbre de Van Emde Boas

Un exemple d'arbre de Van Emde Boas. Dans cet exemple, top est noté aux.

Structure des données	Arbre non binaire

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Arbre de Van Emde Boas

Un exemple d'arbre de Van Emde Boas. Dans cet exemple, top est noté aux.

Découvreur ou inventeur	Peter van Emde Boas
Date de découverte	1975

Complexité en temps
Pire cas	$O(log(log(M)))$
Moyenne	$O(log(log(M)))$
Meilleur cas	$O(log(log(M)))$

Complexité en espace
Pire cas	$O(M)$
Moyenne	$O(M)$
Meilleur cas	$O(M)$

nouveau modèle actuel[modifier | modifier le code]

Arbre de Van Emde Boas

Un exemple d'arbre de Van Emde Boas. Dans cet exemple, top est noté aux.

Découvreur ou inventeur	Peter van Emde Boas
Date de découverte	1975

Complexité en temps
Pire cas	$O(log(log(M)))$
Moyenne	$O(log(log(M)))$
Meilleur cas	$O(log(log(M)))$

Complexité en espace
Pire cas	$O(M)$
Moyenne	$O(M)$
Meilleur cas	$O(M)$

Médiane des médianes[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Médiane des médianes

Problème lié	Algorithme de sélection
Structure des données	Tableau

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Médiane des médianes

Découvreurs ou inventeurs	Manuel Blum, Robert Floyd, Vaughan Pratt (en), Ronald Rivest, Robert Tarjan
Date de découverte	1972^[2]
Problème lié	Algorithme de sélection
Structure des données	Tableau
Basé sur	Quickselect

Complexité en temps
Pire cas	$O(n)$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(\log n)$

nouveau modèle actuel[modifier | modifier le code]

Médiane des médianes

Découvreurs ou inventeurs	Manuel Blum, Robert Floyd, Vaughan Pratt (en), Ronald Rivest, Robert Tarjan
Date de découverte	1972^[2]
Problème lié	Algorithme de sélection
Structure des données	Tableau
Basé sur	Quickselect

Complexité en temps
Pire cas	$O(n)$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(\log n)$

Quickselect[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Quickselect

Problème lié	Algorithme de sélection
Structure des données	Tableau

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Quickselect

Visualisation animée de l'algorithme de sélection rapide. Sélection de la 22ème plus petite valeur.

Découvreur ou inventeur	Charles Antony Richard Hoare
Date de découverte	1961
Problème lié	Algorithme de sélection
Structure des données	Tableau
À l'origine de	Médiane des médianes

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n)$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)$

nouveau modèle actuel[modifier | modifier le code]

Quickselect

Visualisation animée de l'algorithme de sélection rapide. Sélection de la 22ème plus petite valeur.

Découvreur ou inventeur	Charles Antony Richard Hoare
Date de découverte	1961
Problème lié	Algorithme de sélection
Structure des données	Tableau
À l'origine de	Médiane des médianes

Complexité en temps
Pire cas	$O(n^{2})$
Moyenne	$O(n)$
Meilleur cas	$O(n)$

Complexité en espace
Pire cas	$O(1)$

Algorithme de Hopcroft-Karp[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Algorithme de Hopcroft-Karp

Problème lié	Couplage (théorie des graphes)
Structure des données	Graphe biparti

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme de Hopcroft-Karp

Découvreurs ou inventeurs	John Hopcroft, Richard Karp, Alexander V. Karzanov (en)
Date de découverte	1973
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d)
Structure des données	Graphe
Basé sur	Algorithme hongrois

Complexité en temps
Pire cas	$O(E{\sqrt {V}})$

Complexité en espace
Pire cas	$O(V)$

nouveau modèle actuel[modifier | modifier le code]

Algorithme de Hopcroft-Karp

Découvreurs ou inventeurs	John Hopcroft, Richard Karp, Alexander V. Karzanov (en)
Date de découverte	1973
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d)
Structure des données	Graphe
Basé sur	Algorithme hongrois

Complexité en temps
Pire cas	$O(E{\sqrt {V}})$

Complexité en espace
Pire cas	$O(V)$

Algorithme de Johnson[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

Algorithme de Johnson

Problème lié	Plus courts chemins entre tous les sommets
Structure des données	Graphe

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Algorithme de Johnson

Découvreur ou inventeur	Donald B. Johnson (en)
Date de publication	1977
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d), problèmes de cheminement
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|V\|^{2}\log \|V\|+\|V\|\|E\|)$

nouveau modèle actuel[modifier | modifier le code]

Algorithme de Johnson

Découvreur ou inventeur	Donald B. Johnson (en)
Date de publication	1977
Problèmes liés	Algorithme, algorithme de la théorie des graphes (d), problèmes de cheminement
Structure des données	Graphe

Complexité en temps
Pire cas	$O(\|V\|^{2}\log \|V\|+\|V\|\|E\|)$

exemple[modifier | modifier le code]

ancien modèle[modifier | modifier le code]

nouveau modèle brouillon[modifier | modifier le code]

Brouillon!

Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua suite 1

nouveau modèle actuel[modifier | modifier le code]

Suaudeau/Bac à sable/test sur l'Infobox Algorithme Lua suite 1

↑ ^{a et b} R. Bayer et E. McCreight, « Organization and maintenance of large ordered indices », SIGFIDET '70: Proceedings of the 1970 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control, ACM,‎ novembre 1970, p. 107-141 (ISBN 978-1-4503-7941-0, DOI 10.1145/1734663.1734671)
↑ ^{a et b} (en) Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest et Robert E. Tarjan, « Time bounds for selection », Journal of Computer and System Sciences, Elsevier, vol. 7, n^o 4,‎ août 1973, p. 448-461 (ISSN 0022-0000 et 1090-2724, DOI 10.1016/S0022-0000(73)80033-9)

[wikidata-8b276371ef944464ae99b0d28d05e4f8c4a98c8dQ61783186-1] {a et b} R. Bayer et E. McCreight, « Organization and maintenance of large ordered indices », SIGFIDET '70: Proceedings of the 1970 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control, ACM,‎ novembre 1970, p. 107-141 (ISBN 978-1-4503-7941-0, DOI 10.1145/1734663.1734671)

[wikidata-8bfb307d4a12c04e302ae05e204046dea379a837Q55881151-2] {a et b} (en) Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest et Robert E. Tarjan, « Time bounds for selection », Journal of Computer and System Sciences, Elsevier, vol. 7, n^o 4,‎ août 1973, p. 448-461 (ISSN 0022-0000 et 1090-2724, DOI 10.1016/S0022-0000(73)80033-9)

[1]

[2]